﻿using System;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            //ListNode node5 = new ListNode(9);
            //ListNode node4 = new ListNode(9,node5);
            //ListNode node3 = new ListNode(9,node4);
            //ListNode node2 = new ListNode(9, node3);
            //ListNode node1 = new ListNode(4);
            //ListNode node = new ListNode(2, node1);
            //ListNode root = new ListNode(1, node);

            //ListNode node13 = new ListNode(9);
            //ListNode node12 = new ListNode(4);
            //ListNode node11 = new ListNode(3, node12);
            //ListNode root1 = new ListNode(1, node11);

            ListNode root = null;
            ListNode root1 = new ListNode();

            var result = MergeTwoLists(root, root1);

            Console.WriteLine("Hello World!");
        }

        /// <summary>
        /// 两数相加
        /// </summary>
        /// <param name="l1"></param>
        /// <param name="l2"></param>
        /// <returns></returns>
        public static ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            ListNode list = new ListNode();
            int temp = 0;
            list.val = (l1.val + l2.val + temp) % 10;
            temp = (l1.val + l2.val + temp) >= 10 ? (l1.val + l2.val + temp) / 10 : 0;
            if ((l1 == null || l1.next == null) && (l2 == null || l2.next == null) && temp == 0)
                return list;
            list.next = new ListNode();
            ListNode node = list.next;
            while (l1 != null || l2 != null)
            {
                if (l1 != null)
                    l1 = l1.next;
                else
                {
                    l1 = null;
                }
                if (l2 != null)
                    l2 = l2.next;
                else
                {
                    l2 = null;
                }
                int temp1 = l1 == null ? 0 : l1.val;
                int tem2 = l2 == null ? 0 : l2.val;
                node.val = (temp1 + tem2 + temp) % 10;
                temp = (temp1 + tem2 + temp) >= 10 ? (temp1 + tem2 + temp) / 10 : 0;
                if ((l1 == null || l1.next == null) && (l2 == null || l2.next == null) && temp == 0)
                    return list;
                node.next = new ListNode();
                node = node.next;
            }
            return list;
        }

        /// <summary>
        /// 21. 合并两个有序链表
        /// </summary>
        /// <param name="l1"></param>
        /// <param name="l2"></param>
        /// <returns></returns>
        public static ListNode MergeTwoLists(ListNode l1, ListNode l2)
        {
            ListNode result = new ListNode();
            if (l1 == null && l2 == null)
                return null;
            if (l1 == null)
            {
                result = l2;
                return result;
            }
            if (l2 == null)
            {
                result = l1;
                return result;
            }
            if (l1.val < l2.val)
            {
                result.val = l1.val;
                l1 = l1.next;
            }
            else
            {
                result.val = l2.val;
                l2 = l2.next;
            }
            result.next = new ListNode();
            ListNode node = result.next;
            while (l1 != null || l2 != null)
            {
                if (l1 == null)
                {
                    node.val = l2.val;
                    node.next = l2.next;
                    return result;
                }
                if (l2 == null)
                {
                    node.val = l1.val;
                    node.next = l1.next;
                    return result;
                }
                if (l1.val <= l2.val)
                {
                    node.val = l1.val;
                    l1 = l1.next;
                }
                else
                {
                    node.val = l2.val;
                    l2 = l2.next;
                }
                node.next = new ListNode();
                node = node.next;
            }
            return result;
        }

        #region Common Class
        public class ListNode
        {
            public int val;
            public ListNode next;
            public ListNode(int val = 0, ListNode next = null)
            {
                this.val = val;
                this.next = next;
            }
        }
        #endregion

    }
}
